let MAX = Infinity;
let graph = [
  [0, 34, 46, MAX, MAX, 19],
  [34, 0, MAX, MAX, 12, MAX],
  [46, MAX, 0, 17, MAX, 25],
  [MAX, MAX, 17, 0, 38, 25],
  [MAX, 12, MAX, 38, 0, 26],
  [19, MAX, 25, 25, 26, 0]
];




// 初始化parent数组
function genParent(graph) {
    let parent = [];
    let vertexNum = graph.length;
    for(let i = 0; i < vertexNum; i++) {
        parent[i] = -1;
    }
    return parent; // 返回parent数组
}

// 生成边集
function genEdges(graph) {
    let edges = [];
    let vertexNum = graph.length;
    for(let i = 0; i < vertexNum; i++) {
        for(let j = i + 1; j < vertexNum; j++) {
            if(graph[i][j] != MAX) {
                edges.push({
                    from: i,
                    to: j,
                    weight: graph[i][j]
                })
            }
        }
    } 
    
    return edges.sort((a,b) => (a.weight - b.weight));
}

// 查找当前顶点的根节点
function findRoot(parent, v) {
    let t = v; // 处理扁平化数据的一种方式，数组元素下标作为顶点，数组元素值作为双亲结点
    while(parent[t] != -1) {
        t = parent[t];
    }

    return t;
}

function output(from, to) {
    console.log(from + ' -> ' + to);
}

function kruskal(g) {
    let parent = genParent(g);
    let edges = genEdges(g);
    
    let nums = graph.length,
        cnt = 0;
    edges.forEach(e => {
        let v1 = findRoot(parent, e.from);
        let v2 = findRoot(parent, e.to);
        if(v1 != v2) {
            output(e.from, e.to);
            parent[v2] = v1;
            cnt++;
            if(cnt < nums - 1) 
                return ;
        }
    })
}

kruskal(graph);

/**
1 -> 4
2 -> 3
0 -> 5
2 -> 5
4 -> 5
 */






